<?php
$m = new Moneda();
$monedas = array(1,4,6);
$cambio =8;
$m->seleccion_monedas($cambio,$monedas, $m->monedas($cambio, $monedas)) ;

class Moneda {
    
    function debug($ar){
        echo '<pre>';
        print_r($ar);
        echo '</pre>';
    }
   function seleccion_monedas($c, $monedas, $tabla){
        
		//int[] seleccion = new int[monedas.length];
		for($i = 0; $i< count($monedas); $i++){
			$seleccion[$i]=0;
		}
		$i= count($monedas);
       // echo $i;
		$j= $c;
		while($j>0){
			if($i>=1 && ($tabla[$i][$j] == $tabla[$i-1][$j])){
				$i--;
			}
			else{
				$seleccion[$i] = $seleccion[$i] + 1;
				$j = $j - $monedas[$i-1];
			}
		}
        /*
		for($i = 0; $i< count($seleccion); $i++){
			echo "mons ".$seleccion[$i];
		}*/
        $this->debug($seleccion);
    }
    function monedas($cantidad_devuelta, $monedas){
        $matriz_cambio = array();
        
        for($i = 0; $i <= count($monedas); $i++)
		     $matriz_cambio[$i][0] = 0;	  
		 
		for($j = 0; $j <= $cantidad_devuelta; $j++)
		     $matriz_cambio[0][$j] = 99;	
        
       
        
        for( $i = 1; $i <= count($monedas) ; $i++){
            for( $j = 1; $j <= $cantidad_devuelta; $j++){
                if($j < $monedas[$i-1] ){

                   $matriz_cambio[$i][$j] = $matriz_cambio[$i-1][$j]; 
                }else{

                    $minimo = 0; 

                    if($matriz_cambio[$i-1][$j] < $matriz_cambio[$i][$j - $monedas[$i-1]] + 1){
                       $minimo = $matriz_cambio[$i-1][$j];
                    }else{
                       $minimo = $matriz_cambio[$i][$j - $monedas[$i-1]] + 1;
                    }

                    $matriz_cambio[$i][$j] = $minimo;
                    //System.out.println("minimo"+minimo);
                }
            }
        }
        $this->debug($matriz_cambio);
        for($i = 0;$i <= count($monedas); $i++){
            for($j = 0; $j< $cantidad_devuelta+1; $j++){
                echo "[".$matriz_cambio[$i][$j]."]";
            }
            echo "<br>";
        }
        echo "cant monedas a pagar: ".$matriz_cambio[count($monedas)][$cantidad_devuelta];
        return $matriz_cambio;
       //return "cant monedas ". $matriz_cambio[count($monedas)][$cantidad_devuelta] ;
    }
}
?>
